import java.util.LinkedList;
import java.util.ArrayList;
/**
 * This BST doesn't handle duplicates
 * In order to do so, you have to correct it yourslef.
 * @author ldong
 *
 * @param <T>
 */


public class BinarySearchTree<T extends Comparable<? super T>> {

	
	private Node<T> root;
	private int size;
	private ArrayList<T> treeArrayList;
	
	public BinarySearchTree()
	{
		size = 0;
		root = null;
	}

	/**
	 * Insertion wrapper in recursion
	 * @param data
	 */
	public void insertByRecursion(T data)
	{
		if(root == null)
		{
			root = new Node<T>(data);
			size++;
		}
		else // if its not the first node
		{
			if(data == null)
				return;
			insert(data, root); 
		}
	}
	
	/**
	 * Recursive Insertion Helper function
	 * @param data
	 * @param node
	 */
	public void insert(T data, Node<T> node)
	{

		if(node == null)
		{
			node = new Node<T>(data);
			size++;
			return;
		}
	
		if(data.compareTo(node.getData()) == 0)
		{// do nothing if they are the same
			return;
		}
		else if (data.compareTo(node.getData()) < 0)
		{ // if data is less than the node data
			
			if(node.left == null)
				node.left = new Node<T>(data);
			
			insert(data, node.left);
		}
		else if (data.compareTo(node.getData()) > 0)
		{// if data is greater than the node data
		
			if(node.right == null)
				node.right = new Node<T>(data);
			
			insert(data, node.right);
		}
		
	}
	
	public void insertByLoop(T data)
	{
		if(root == null)
		{
			root = new Node<T>(data);
			size++;
			return;
		}
		else
		{
			Node<T> current = root;
			
			while(current != null)
			{
			    if(data.compareTo(current.getData()) > 0)
			    {
			    	if(null ==  current.right)
			    	{
			    		current.right = new Node<T>(data);
			    		size++;
			    		return;
			    	}
			    	else
			    		current = current.right;
			    }
			    else if(data.compareTo(current.getData()) < 0)
			    {
			    	if(null == current.left)
			    	{
			    		current.left = new Node<T>(data);
			    		size++;
			    		return;
			    	}
			    	else
			    		current = current.left;
			    }
			    else
			       return; // does not handle duplicates
			}
		}
	}
	
	
	/***************   Working on it      **********/
	/**
	 * Deletion wrapper
	 * @param data
	 */
	public void delete(T data)
	{
		if(root.left == null && root.right == null)
		{
			if(data.compareTo(root.data) == 0)
				root = null;
			else
				return;
		}
		
		if(root.left == null)
		{
			delete(data, root.right, root);
		}
		else if(root.right == null)
		{
			delete(data, root.left, root);
		}
		else // if both children exist
		{
			delete(data, root.right, root);
			delete(data, root.left, root);
		}
		
	}
	/******/
	public void delete(T data, Node<T> node)
	{
		if(null == node)
			return;
		
		if(data.compareTo(node.data)<0)
			delete(data,node.left);
		else if(data.compareTo(node.data)>0)
			delete(data,node.right);
		else{
			if(node.left == null && node.right == null){
				
				node = null;
				return;
			}
			else if(node.left == null){
				Node<T> tempNode = node;
				node = node.right;
				//delete tempNode
			}
			else if(node.right == null){
				Node<T> tempNode = node;
				node = node.left;
				//delete tempNode
			}
			else{
				Node<T> tempNode = findMin(node.right);
				node.data = tempNode.data;
				delete(node.data, node.right);
			}
		}
		
	}
	
	/*************/
	   /* remove a value from the tree, if it exists
     * @param	key such that value.compareTo(key) == 0 for the node to remove
     * @param	node the root of the subtree from which to remove the value
     * @return	the new tree with the value removed
     */
    protected Node<T> remove(T value, Node<T> node) {
	if (node == null) {	// key not in tree
	    return null;
	}
	if (value.compareTo(node.data) == 0) { // remove this node
	    if (node.left == null) { // replace this node with right child
		return node.right;
	    } else if (node.right == null) { // replace with left child
		return node.left;
	    } else {
		// replace the value in this node with the value in the
		// rightmost node of the left subtree
		node = findMin(node.left);
		// now remove the rightmost node in the left subtree,
		// by calling "remove" recursively
                node.left = remove(node.data, node.left);
		// return node;  -- done below
	    }
	} else {		// remove from left or right subtree
	    if (value.compareTo(node.data) < 0) {
		// remove from left subtree
		node.left = remove(value, node.left);
	    } else {		// remove from right subtree
		node.right = remove(value, node.right);
	    }
	}
	return node;
    }	
	
	
	
	
	
	
	/**************/
	/**
	 * Deletion Helper Function
	 * @param data
	 * @param node
	 */
	public void delete(T data, Node<T> node, Node<T> parent)
	{
		if(node == null /*|| parent == null*/) // do nothing
			return;
		
		if(data.compareTo(node.getData())<0)
		{
			delete(data, node.left, node);
		}
		else if(data.compareTo(node.getData())>0)
		{
			delete(data,node.right, node);
		}
		else // if found they have the same data 
		{
			System.out.print("found target -> ");
			
			// decrease the size if found the data
			size--;
			
			if(node.left == null && node.right == null) 
			{// its a leaf node
				System.out.println(" leaf node");
				
				if(parent.left == node)
					parent.left = null;
				else
					parent.right = null;
				
				return;
			}
			else if(node.left == null) 
			{// it only has right child
				System.out.println(" right child");

				if(parent.left == node)
					parent.left = node.right;
				else
					parent.right = node.left;
				
				return;
			}
			else if(node.right == null)
			{ // it only has left child
				System.out.println(" left child");
				
				parent.right = node.left;
				
				return;
			}
			else // it has two children
			{
				System.out.println(" both children");
				
				
				if(parent.left == node)
				{
					parent.left = findMin(node.right);
				}
				else
				{
					parent.right = findMin(node.right);
				}
				
				return;
			}
			
		}			
	}


	
	// find the data
	public Node<T> find(T data, Node<T> node)
	{
	  if(node == null)
		  return null;
	  if(data.compareTo(node.getData())==0)
	  {
		  return node;
      }
	  else if(data.compareTo(node.getData())<0)
	  {
		  return find(data, node.left);
	  }
	  else
		  return find(data, node.right);
	}
	
	
	public int maxHeight()
	{
		return Height(root);
	}
	
	
	public int Height(Node<T> node)
	{
		Node<T> current = node;

		if(current.left != null)
		{
			Node<T> left = current.left;
		}
		if(current.right!= null)
		{
			Node<T> right = current.right;
		}
		
		int height = 0;
		while(!(current.left == null && current.right ==null))
		{
			if(current.left != null)
				current = current.left;
			if(current.right!= null)
				current = current.right;
		}
		return height;
	}
	
	
	public Node<T> findMin()
	{
		return findMin(root);
	}
	
	// find the most left child of node's subtree
	public Node<T> findMin(Node<T> node)
	{
		if(node == null)
			return null;
		
		if(node.left == null)
			return node;
		
		return findMin(node.left);
	}
	
	
	
	public int getSize() {
		return size;
	}

	/************************/
	public void printPreOrder()
	{
		printPreOrder(root);

	}
	public void printPreOrder(Node<T> node)
	{
		if(node == null)
			return;
		System.out.print(node+ " ->");

		printPreOrder(node.left);
		printPreOrder(node.right);
	}
	/************************/
	public void printInOrder()
	{
		printInOrder(root);
	}

	public void printInOrder(Node<T> node)
	{
		if(node == null)
			return;
		printInOrder(node.left);
		System.out.print(node+" ->");
		printInOrder(node.right);

	}
	/************************/
	public void printPostOrder()
	{
		printPostOrder(root);
	}
	
	public void printPostOrder(Node<T> node)
	{
		if(node == null)
			return;
		printPostOrder(node.left);
		printPostOrder(node.right);
		System.out.print(node+" ->");
	}
	/************************/
	
	public void printLevelOrder()
	{
		if(root != null)
		{
			Node<T> current = root;
			LinkedList<Node<T>> q1 = new LinkedList<Node<T>>();
			LinkedList<Node<T>> q2 = new LinkedList<Node<T>>();

			q1.add(current);
			
			while(!(q1.isEmpty() && q2.isEmpty()))
			{
				while(!q1.isEmpty())
				{
					current = q1.poll();
					System.out.print(current);

					if(current.left != null)
						q2.add(current.left);
					if(current.right != null)
						q2.add(current.right);
				}
				System.out.println();

				while(!q2.isEmpty())
				{
					current = q2.poll();
					System.out.print(current);

					if(current.left != null)
						q1.add(current.left);
					
					if(current.right != null)
						q1.add(current.right);
				}
				System.out.println();
			}
		}
	}
	
	/**** Verify if the array list is a valid binary search tree ******/
	
	
	public boolean isBST(ArrayList<T> list)
	{
		boolean mark = true;
		
		arrayInOrder();
		
		if(list.size() == treeArrayList.size())
			for(int i = 0; i< list.size(); i++)
			{
				// if they are not the same, mark false and exit the loop
				if(!(list.get(i) == treeArrayList.get(i)))
				 {
					mark = false;
					break;
				 }
			}
		else // not the same size, return false
			return false;
		
		return mark;
	}
	
	
	public boolean isBSTree()
	{
		boolean mark = true;
		
		arrayInOrder();
		
		for(int i = 0; i< treeArrayList.size()-1; i++)
		{
			if(treeArrayList.get(i).compareTo(treeArrayList.get(i+1)) >0)
					return mark = false;
		}
		
		return mark;
	}
	
	
	public boolean isBSTree(Node<T> node)
	{
		treeArrayList = new ArrayList<T>();
		arrayInOrder(node);
		
		boolean mark = true;
		
		for(int i = 0; i< treeArrayList.size()-1; i++)
		{
			if(treeArrayList.get(i).compareTo(treeArrayList.get(i+1)) >0)
					return mark = false;
		}
		
		return mark;
	}
	
	public void arrayInOrder()
	{
		treeArrayList = new ArrayList<T>();
		arrayInOrder(root);

	}
	public void arrayInOrder(Node<T> node)
	{
		if(node == null)
			return;
		arrayInOrder(node.left);
			treeArrayList.add(node.data);
		arrayInOrder(node.right);
	}

	/****************************************************
	 * Print outputs of the orders
	 * 
	 */
	public void printOutputs()
	{
	    System.out.println("PreOrder");
	    printPreOrder();
	    System.out.println();

	    System.out.println("InOrder");
	    printInOrder();
	    System.out.println();

	    System.out.println("PostOrder");
	    printPostOrder();

	    System.out.println("\nTree");
	    printLevelOrder();
	    System.out.println();
		
	}
	
	


}
